/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.ds;

import java.util.HashMap;
import java.util.Map;

/**
 * <p>串树的实现</p>
 * @author towan
 * @email tongwenzide@163.com
 * 2015年5月21日
 */

class TrieNode {
    // Initialize your data structure here.
    boolean isWord;
    Map<Character,TrieNode> children;
    public TrieNode() {
        children  = new HashMap<>();
    }
}


public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // Inserts a word into the trie.
    public void insert(String word) {
        char[] chs = word.toCharArray();
        TrieNode p = root;
        int i = 0;
        int n = chs.length;
        
        //遍历存在的字符
        while(i<n){
            TrieNode next = p.children.get(chs[i]);
            
            if(next!=null){
                p = next;
                i++;
            }else{
                break;
            }
        }
        //追加到新节点
        while(i<n){
            TrieNode newTrie = new TrieNode();
            p.children.put(chs[i], newTrie);
            p =  newTrie;
            i++;
        }
        //set word end
        p.isWord = true;
    }

    // Returns if the word is in the trie.
    public boolean search(String word) {
        TrieNode p = root;
        for(int i=0;i<word.length();i++){
            char ch = word.charAt(i);
            TrieNode child = p.children.get(ch);
            if(child==null){
                return false;
            }
            p = child;
        }
        return p.isWord;
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
        TrieNode p = root;
        for(int i=0;i<prefix.length();i++){
            TrieNode child = p.children.get(prefix.charAt(i));
            if(child==null){
                return false;
            }
            p = child;
        }
        return true;

    }
    public static void main(String[] args) {
         Trie trie = new Trie();
         trie.insert("somestring");
         trie.insert("key");
         System.out.println(trie.search("key"));
    }
}

    // Your Trie object will be instantiated and called as such:
    // Trie trie = new Trie();
    // trie.insert("somestring");
    // trie.search("key");
